// https://leetcode.cn/problems/binary-tree-paths/description/

// 算法思路总结：
// 1. 深度优先搜索遍历二叉树所有路径
// 2. 递归构建路径字符串，使用"->"连接节点
// 3. 到达叶子节点时将完整路径加入结果
// 4. 回溯时自动恢复路径状态（字符串传值）
// 5. 时间复杂度：O(n)，空间复杂度：O(h)（递归栈深度）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    vector<string> ret;
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        string path;
        ret.clear();
        dfs(root, path);

        return ret;
    }

    void dfs(TreeNode* root, string path)
    {
        if (root->left == nullptr && root->right == nullptr)
        {
            path += to_string(root->val);
            ret.push_back(path);
            return ;
        }

        path += to_string(root->val);
        path += "->";

        if (root->left) dfs(root->left, path);
        if (root->right) dfs(root->right, path);

        return ;
    }
};

int main()
{
    vector<string> tree1 = {"1", "2", "3", "null", "5"};
    vector<string> tree2 = {"1"};

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    auto vs1 = sol.binaryTreePaths(root1);
    auto vs2 = sol.binaryTreePaths(root2);

    for (const string& str : vs1)
        cout << str << " ";
    cout << endl;

    for (const string& str : vs2)
        cout << str << " ";
    cout << endl;   

    return 0;
}